package problem_everyday;

public class D2025_06_26_P2311 {
    private String tansfer_to_bit2(int k, int length){
        String s = Integer.toBinaryString(k);
        int pre_zero_num = length - s.length();
        if(pre_zero_num > 0)
            s = "0".repeat(pre_zero_num) + s;
        return s;
    }

    public int longestSubsequence(String s, int k) {
        /*
        * 找出s的最长子序列，需要满足如下的要求：
        *   可以删除其中若干的元素，但不能改变其排列顺序
        *   可以存在前导0
        *   将该子序列转换为 二进制值，其大小不大于k
        *   如果是空串的话，其对应的值为0
        * */

        /*
        * 111000 ... 01
        * 如果将第i位的字符删除，相当于将其前 i-1个值都除以2倍
        * */
        String k_bits = tansfer_to_bit2(k, s.length());
        if(k_bits.length() > s.length()) return s.length();
        int zero_count = 0;
        int i = 0;
        while(k_bits.charAt(i) == '0'){
            if(s.charAt(i) == '0'){
                zero_count ++;
            }
            i++;
        }
        int res = zero_count + s.length() - i;

        for(int j=i; j<s.length(); j++){
            // 先在某一位上发现小于，说明不用再删除；
            if(s.charAt(j) < k_bits.charAt(j)){
                return res;
            } else if(s.charAt(j) > k_bits.charAt(j)){
                return res-1;
            }
        }
        return res;
    }

    public static void main(String[] args){
        String s = "111100010000011101001110001111000000001011101111111110111000011111011000010101110100110110001111001001011001010011010000011111101001101000000101101001110110000111101011000101";
        int k = 11713332;
        D2025_06_26_P2311 p = new D2025_06_26_P2311();
        int res = p.longestSubsequence(s, k);
        System.out.println(res);
    }
}
